package com.atwulidun.linkedlist;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode hero5 = new HeroNode(5, "秦明", "霹雳火");
        HeroNode hero6 = new HeroNode(6, "柴进", "小旋风");

        SingleLinkedList singleLinkedList = new SingleLinkedList();
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();


        // 添加
        // 依次添加到链表的尾部
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero4);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero2);

        // 按照no从小到大的顺序添加到链表中
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero5);
//        singleLinkedList.addByOrder(hero2);

        singleLinkedList1.addByOrder(hero2);
        singleLinkedList1.addByOrder(hero4);
        singleLinkedList1.addByOrder(hero6);

//        SingleLinkedList.mergeTwoLinkedList(singleLinkedList1.getHead(), singleLinkedList.getHead());// 方式一
//        HeroNode heroNode1 = SingleLinkedList.mergeTwoLinkedListRecursive(singleLinkedList1.getHead().next, singleLinkedList.getHead().next);// 方式二
//        HeroNode heroNode2 = SingleLinkedList.mergeTwoLinkedListPreEnd(singleLinkedList1.getHead(), singleLinkedList.getHead());// 方式三
//        singleLinkedList.list();
//        HeroNode heroNode = new HeroNode(0, null, null);
//        heroNode.next = heroNode1;
//        SingleLinkedList.list(heroNode);

        // 修改(测试修改第一个和最后一个能否成功)
//        System.out.println("修改之前：");
//        singleLinkedList.list();
//        HeroNode newHeroNode1 = new HeroNode(1, "江江", "小雨雨");
//        HeroNode newHeroNode4 = new HeroNode(4, "冲冲", "小豹子");
//        singleLinkedList.update(newHeroNode1);
//        singleLinkedList.update(newHeroNode4);
//        System.out.println("修改之后：");
//        singleLinkedList.list();
//        System.out.println("当前的有效节点数为：" + SingleLinkedList.getLength(singleLinkedList.getHead()));
//        System.out.println(SingleLinkedList.getLastIndexNode(singleLinkedList.getHead(), 1));
//        System.out.println(SingleLinkedList.getLastIndexNode(singleLinkedList.getHead(), 4));
//        System.out.println(SingleLinkedList.getLastIndexNode(singleLinkedList.getHead(), 0));
//        System.out.println(SingleLinkedList.getLastIndexNode(singleLinkedList.getHead(), 5));

        // 删除(测试删除第一个和最后一个能否成功)
//        System.out.println("删除之前：");
//        singleLinkedList.list();
//        singleLinkedList.delete(1);
//        singleLinkedList.delete(4);
//        System.out.println("当前的有效节点数为：" + SingleLinkedList.getLength(singleLinkedList.getHead()));
//        singleLinkedList.delete(2);
//        singleLinkedList.delete(3);
//        System.out.println("删除之后：");
//        singleLinkedList.list();
//        System.out.println("当前的有效节点数为：" + SingleLinkedList.getLength(singleLinkedList.getHead()));

//        singleLinkedList.list();
//        SingleLinkedList.reverseLinkedList(singleLinkedList.getHead());
//        singleLinkedList.list();

//        SingleLinkedList.reversePrint(singleLinkedList.getHead());// 用栈的方式实现
//        SingleLinkedList.reversePrintRecursive(singleLinkedList.getHead());// 用递归的方式实现
    }
}

class SingleLinkedList {
    private final HeroNode head = new HeroNode(0, null, null);

    public HeroNode getHead() {
        return head;
    }

    // 不按照顺序添加
    public void add(HeroNode heroNode) {
        HeroNode temp = head;// 要特别注意，这里不能写成HeroNode temp = head.next;因为temp有可能为null，下面的temp.next会抛出空指针异常
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    // 按照顺序添加
    public void addByOrder(HeroNode heroNode) {
        HeroNode temp = head;
        Boolean flag = false;// 设置一个标志位来标志该英雄是否已经被添加
        while (true) {
            // 情况一：已经遍历到了链表的尾部
            if (temp.next == null) {
                break;
            }
            // 情况二：从前往后编号由小到大遍历，一开始heroNode.no 比 temp.next.no 大，直到小于后停止遍历，没有遍历到链表的尾部
            if (heroNode.no < temp.next.no) {
                break;
            } else if (heroNode.no == temp.next.no) {// 情况三：该英雄已经被添加过
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.println("英雄\"" + heroNode.name + "\"已经被添加过！");
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    // 根据编号来修改英雄的信息
    public void update(HeroNode heroNode) {
        // 首先判断一下链表是否为空
        if (head.next == null) {
            System.out.println("链表为空，不能修改！");
            return;
        }
        // 设立一个标志位来标志是否找到要修改的节点
        Boolean flag = false;
        // 新建一个辅助节点
        HeroNode temp = head.next;
        while (true) {
            if (temp.no == heroNode.no) {// 说明找到了要修改的节点(temp.no == heroNode.no的判断条件要在temp.next == null之前，
                // 否则，若最后的一个节点刚好就是要修改的节点时会出现找不到的情况)
                flag = true;
                break;
            }
            if (temp.next == null) {// 说明遍历到了链表的最后一个节点都没有找到要修改的节点
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        } else {
            System.out.println("要修改的英雄\"" + heroNode.name + "\"不存在！");
        }
    }
    // 也可以做如下的修改
    public void update1(HeroNode heroNode) {
        // 首先判断一下链表是否为空
        if (head.next == null) {
            System.out.println("链表为空，不能修改！");
            return;
        }
        // 设立一个标志位来标志是否找到要修改的节点
        Boolean flag = false;
        // 新建一个辅助节点
        HeroNode temp = head.next;
        while (true) {
            if (temp == null) {// 说明遍历到了链表的最后一个节点的下一个空结点
                break;
            }
            if (temp.no == heroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        } else {
            System.out.println("要修改的英雄\"" + heroNode.name + "\"不存在！");
        }
    }

    // 根据编号来删除节点
    public void delete(int no) {
        // 一、首先判断一下链表是否为空
        if (head.next == null) {
            System.out.println("链表为空，不能删除！");
            return;
        }
        HeroNode temp = head;// 二、因为需要找到被删除节点的前一个节点，故这里的temp节点直接等于head
        Boolean flag = false;// 设置一个标志位来标志是否找到相应的节点
        while (true) {
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            if (temp.next.next == null) {// 三、如果temp.next.no == no不成立但temp.next.next == null成立，
                // 说明遍历到链表的最后一个节点也没有找到要删除的节点
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("要删除的编号\"" + no + "\"不存在！");
        }
    }
    //
    public void delete2(int no) {
        HeroNode temp = head;// 因为需要找到被删除节点的前一个节点，故这里的temp节点直接等于head
        Boolean flag = false;// 设置一个标志位来标志是否找到相应的节点
        while (true) {
            if (temp.next == null) {// 只有temp.next != null，才能往下走进行temp.next.no == no的判断，否则会出现空指针异常
                break;
            }
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.println("要删除的编号\"" + no + "\"不存在！");
        }
    }

    // 显示链表信息
    public void list() {
        HeroNode temp = head.next;
        if (temp == null) {
            System.out.println("链表为空！");
            return;
        }
        while (true) {
            System.out.println(temp);
            temp = temp.next;
            if (temp == null) {
                break;
            }
        }
    }

    // 根据头结点来显示链表信息
    public static void list(HeroNode headNode) {
        HeroNode temp = headNode.next;
        if (temp == null) {
            System.out.println("链表为空！");
            return;
        }
        while (true) {
            System.out.println(temp);
            temp = temp.next;
            if (temp == null) {
                break;
            }
        }
    }

    // 单链表新浪面试题一：获取单链表节点的个数，若带头结点，则不考虑头结点
    public static int getLength(HeroNode head) {
        int length = 0;
        HeroNode temp = head;
        while (temp.next != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    // 单链表新浪面试题二：查找单链表中的倒数第 k 个结点
    public static HeroNode getLastIndexNode(HeroNode head, int index) {
        // 如果链表为空，直接返回null
        if (head.next == null) {
            return null;
        }
        // 获取链表有效节点的个数
        int size = getLength(head);
        // 判断index的值是否越界
        if (index < 1 || index > size) {
            return null;
        }
        // 查找单链表中的倒数第 k 个结点，相当于顺序查找第size - k个结点
        HeroNode temp = head.next;
        for (int i = 0; i < size - index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    // 腾讯面试题：单链表的反转(包含头结点)
    // 方式一：
    public HeroNode reverseLinkedList(HeroNode head) {
        // 如果链表的有效结点数为0或1，则直接返回
        if (head.next == null || head.next.next == null) {
            return head;
        }
        HeroNode temp = head.next;
        HeroNode next = null;// 创建一个next结点指向temp结点的下一个结点，不然把temp结点取出来后链表的后面部分会丢失
        HeroNode reverseNode = new HeroNode(0, null, null);// 创建一个暂时挂反转链表的头结点
        while (temp != null) {
            next = temp.next;// 把temp下一个结点存在next中
            temp.next = reverseNode.next;// 这句和下面一句是把temp摘出来插入到reverseNode的第一个有效结点的位置
            reverseNode.next = temp;
            temp = next;// 再把next的值赋给temp
        }
        return reverseNode.next;// 再把反转后的链表重新挂到head头结点
    }

    // 方式二：用递归来实现(不包含头结点)
    public HeroNode reverseLinkedListRecursive(HeroNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 这里的temp应该层层返回上去
        HeroNode temp = reverseLinkedListRecursive(head.next);
        head.next.next = head;
        return temp;
    }

    // 百度面试题:从尾到头打印单链表
    // 方式一：用栈来实现
    public static void reversePrint(HeroNode head) {
        Deque<HeroNode> stack = new LinkedList<>();
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        HeroNode temp = head.next;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.poll());
        }
    }

    // 方式二：用递归来实现
    public static void reversePrintRecursive(HeroNode head) {
        // 这里的判断不应该影响递归的结束条件的判断，因此把递归函数独立出来
        if (head.next == null) {
            System.out.println("链表为空，不能打印！");
            return;
        }
        reversePrintRecursive1(head.next);
    }

    // 这里的head不是头结点
    public static void reversePrintRecursive1(HeroNode head) {
        if (head.next != null) {
            reversePrintRecursive1(head.next);
        }
        System.out.println(head);
    }

    // 合并两个有序的单链表，合并之后仍然有序
    // 方式一：结合了 no从小到大添加结点 以及 将单链表反转
    public static HeroNode mergeTwoLinkedList(HeroNode head1, HeroNode head2) {
        if (head1.next == null) {
            return head2;
        }
        if (head2.next == null) {
            return head1;
        }
        HeroNode temp1 = head1.next;
        HeroNode temp1Next = null;// 这里特别要注意：在将head1的一个结点取出来之前，必须要把它的下一个结点给保存起来，不然后面的链就找不到了
        while (temp1 != null) {
            HeroNode temp2 = head2;
            while (true) {
                if (temp2.next == null) {// 说明已经遍历到了head2的最后一个结点
                    break;
                }
                if (temp1.no <= temp2.next.no) {// 找到要插入的结点的位置
                    break;
                }
                temp2 = temp2.next;
            }
            temp1Next = temp1.next;// 要把temp1.next先存起来，因为下面对temp1.next重新赋了值，若不存，那后面的链表就找不到了
            temp1.next = temp2.next;
            temp2.next = temp1;
            temp1 = temp1Next;
        }
        return head2;
    }

    // 方式二：递归
    // 这里不带头结点，第一个结点就是有效结点
    public static HeroNode mergeTwoLinkedListRecursive(HeroNode head1, HeroNode head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        // 新建一个头结点来挂合并好的新链表
        HeroNode mergeNode;
        if (head1.no < head2.no) {
            mergeNode = head1;
            mergeNode.next = mergeTwoLinkedListRecursive(head1.next, head2);
        } else {
            mergeNode = head2;
            mergeNode.next = mergeTwoLinkedListRecursive(head2.next, head1);
        }
        return mergeNode;
    }

    // 方式三：利用pre和end指针，类似于归并排序的方式
    public static HeroNode mergeTwoLinkedListPreEnd(HeroNode head1, HeroNode head2) {
        if (head1.next == null) {
            return head2;
        }
        if (head2.next == null) {
            return head1;
        }
        // 注意：pre是始终不动的！！！！！！！！！！！！！！
        HeroNode pre = new HeroNode(0, null, null), end = pre;
        // 判断条件为：head1或head2有一方先到尾时结束
        while (head1.next != null && head2.next != null) {
            if (head1.next.no < head2.next.no) {
                end.next = head1.next;// 此时head1.next同时挂在了pre和end上，但是pre不动，只有end往后移动
                end = head1.next;// end往后移动到head.next
                head1.next = head1.next.next;// head.next往后移动到下一个结点，下一次end.next重新赋值，则head1.next.next结点及其后面的链就跟end断开了
            } else {
                end.next = head2.next;// 此时head2.next同时挂在了pre和end上，但是pre不动，只有end往后移动
                end = head2.next;// end往后移动到head.next
                head2.next = head2.next.next;// head.next往后移动到下一个结点，下一次end.next重新赋值，则head2.next.next结点及其后面的链就跟end断开了
            }
        }
        // 如果head1先到尾，则把head2.next直接接到end后面即可
        if (head1.next == null) {
            end.next = head2.next;
        }
        // 如果head2先到尾，则把head1.next直接接到end后面即可
        if (head2.next == null) {
            end.next = head1.next;
        }
        return pre;
    }

    // 这里的head1和head2都不是头结点
    public static HeroNode merge(HeroNode head1, HeroNode head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        HeroNode pre = new HeroNode(0, null, null), end = pre;
        while (head1 != null && head2 != null) {
            if (head1.no < head2.no) {
                end.next = head1;
                end = head1;
                head1 = head1.next;
            } else {
                end.next = head2;
                end = head2;
                head2 = head2.next;
            }
        }
        if (head1 == null) {
            end.next = head2;
        } else {
            end.next = head1;
        }
        return pre.next;
    }
}

class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}